package com.fr.lintcode;

import java.util.Set;
import java.util.TreeSet;

import org.junit.Test;

public class Q1690 {

	/**
	 * @param val: the personality value of user
	 * @return: Return their recommend friends' value
	 * 超时
	 */
	public int[] getAns(int[] val) {
		// Write your code here
		if (val == null || val.length <= 1) {
			return new int[0];
		}
		int length = val.length;
		TreeSet<Integer> set = new TreeSet<>();
		int[] rs = new int[length - 1];
		set.add(val[0]);
		for(int i = 1; i < length; i++) {
			rs[i - 1] = getVal(set, val[i]);
			set.add(val[i]);
		}
		return rs;
	}

	private int getVal(TreeSet<Integer> set, int i) {
		int begin = 0; int end = set.size() - 1;
		Integer vals [] = new Integer[set.size()];
		set.toArray(vals);
		while(begin < end) {
			int mid = (begin + end) / 2;
			if(vals[mid] >= i) {
				end = mid;
			}else {
				if(begin == mid) {
					break;
				}
				begin = mid;
			}
		}
		int min = vals[begin] - i;
		int index1 = begin;
		if(min == 0) {
			return vals[begin];
		}
		end = set.size() - 1;
		while(begin < end) {
			int mid = (begin + end) / 2;
			if(vals[mid] < i) {
				begin = mid + 1;
			}else {
				end = mid;
			}
		}
		int max = vals[begin] - i;
		int index2 = begin;
		
		return max >= Math.abs(min) ? vals[index1] : vals[index2];
	}

	
	@Test
	public void testA() {
		int val[] = {42513,634109,796545,10042,858796,798261,965961,251849};
		int rs[] = getAns(val);
		for(int s : rs) {
			System.out.print(s +",");
		}
		
	}
}
